<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3094：[Acm BeiJing2012]Peach Blossom Spring</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Acm BeiJing2012]Peach Blossom Spring</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Acm BeiJing2012]Peach Blossom Spring</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Acm BeiJing2012]Peach Blossom Spring                </h1>
                <p>时间限制：10s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p><span style="font-size: medium">Tao Yuanming(365-427) was a Chinese poet of Eastern Jin dynasty. One of his most famous works is &quot;Peach Blossom Spring&quot;, which is a fable about a chance<br />
discovery of an ethereal village where the people lead an ideal existence in harmony with nature, unaware of the outside world for centuries. So in Chinese, &quot;Peach Blossom Spring&quot; means &quot;utopia&quot;.<br />
In the story of &quot;Peach Blossom Spring&quot;, there was a mysterious place. In Qin dynasty, some people escaped to that place during the civil unrest and built a village. They and their descendants never left and never had any contact with the outside world since then, until centuries latter a fisherman of Jin dynasty found them.<br />
Recently, some Chinese ACMers happened to find the relics of the village mentioned in&quot;Peach Blossom Spring&quot;.<br />
They also found a document about building hiding places to escape from Qin army. The document said:<br />
There were n houses and m roads in the village. Each road connected two houses. These houses were numbered from 1 to n. There were k families, each living in a different house. <br />
The houses they lived were house 1, house 2, &hellip; , house k. There were also k broken houses: house n-k+1, house n-k+2, ... , house n, with secret basements so that those houses could be used as hiding places.<br />
The problem was that all roads were broken. People wanted to repair some roads so that every family could reach a hiding place through the repaired roads. Every hiding place could only hold one family. Each road cost some labor to be repaired. The head of the village wanted to find out the minimum cost way of repairing the roads, but he didn't know how to do.<br />
Would you solve the problem which the ancient village head never solved?</span></p></p><hr/><h3>输入格式</h3><p><div class="panel_content"><span style="font-size: medium">the first line begins with three integers ---- the above mentioned <span style="color: #ff0000">n (n&lt;=7000), m (0&lt;=m&lt;=10000) </span>and k (1&lt;=k&lt;=5, 2k&lt;=n). Then m lines follow, each containing three integers u,v and w, indicating that there is a broken road connecting house u an d v, and the cost to repair that road is w(1&lt;=w&lt;=1000).</span></div></p><hr/><h3>输出格式</h3><p><div class="panel_content"><span style="font-size: medium">&nbsp;if you cannot find a proper way to repair the roads, output&nbsp; <span style="color: #ff0000">-1</span>&nbsp;&nbsp;in a line. Otherwise, output the minimum cost to repair the roads in a line.</span></div>
<div class="panel_bottom"></div>
<div class="panel_content">
<pre>
	</pre>
</div></p><hr/><h3>样例输入</h3><pre>input 1
4 3 1
4 2 10
3 1 9
2 3 10

input 2
6 7 2
1 5 1000
2 6 1000
1 3 1
2 3 1
3 4 1
4 5 1
4 6 1
 

 


</pre><hr/><h3>样例输出</h3><pre>output 1
29


output 2
5</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>斯坦纳树</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3094" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3094" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>